package com.wh.codedemon.datastructure;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰计算器(后缀表达式)
 *
 * @auther whoo7
 * @date 2024/1/27 11:31
 */
public class ReversePolandCalculator {
    public static void main(String[] args) throws Exception {
        // 先把一个算式转成后缀表达式
        // (29+3)-2*4  ===> 29 3 + 2 4 * - ===> 24
        // 中缀转后缀
//        String suffixExpression = "29 3 + 2 4 * -";
//        String[] items = suffixExpression.split(" ");
        String infixExpression = "( 29 + 3 ) - 2 * 4";
        List<String> suffixExpression = convert2SuffixExpression(infixExpression);
        calculate(suffixExpression);

    }

    private static List<String> convert2SuffixExpression(String infixExpression) {
        String[] items = infixExpression.split(" ");
        Stack<String> s1 = new Stack<>();
        List<String> suffixExpression = new ArrayList<>();
        for (String item : items) {
            if (item.matches("\\d+")) {
                suffixExpression.add(item);
            } else {
                // 如果是操作符
                if (item.equals("(")) {
                    // 压入栈
                    s1.push(item);
                } else if (item.equals(")")) {
                    // 如果是括号结尾,将前面s1中的,也就是括号内的数,压入栈
                    while (!s1.isEmpty() && !s1.peek().equals("(")) {
                        suffixExpression.add(s1.pop());
                    }
                    // 把(给丢掉
                    s1.pop();
                } else {
                    // 操作符加入,如果s1存入的操作符优先级 > 新的,则把s1里的操作符先加进去
                    while (!s1.isEmpty() && getPriority(s1.peek()) >= getPriority(item)) {
                        suffixExpression.add(s1.pop());
                    }
                    s1.push(item);
                }
            }
        }
        // 将s1中剩余的运算符加入到表达式中
        while (!s1.isEmpty()){
            suffixExpression.add(s1.pop());
        }

        return suffixExpression;
    }

    private static int getPriority(String item) {
        return switch (item) {
            case "+", "-" -> 0;
            case "*", "/" -> 1;
            default -> -1;
        };
    }

    private static void calculate(List<String> items) throws Exception {
        Stack<String> stack = new Stack<>();
        for (String item : items) {
            if (item.matches("\\d+")) {
                // 如果是数字  压入栈里
                stack.push(item);
            } else {
                // 如果是操作符,从栈中弹出两个进行晕算
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int result = switch (item) {
                    case "+" -> num1 + num2;
                    case "-" -> num1 - num2;
                    case "*" -> num1 * num2;
                    case "/" -> num1 / num2;
                    default -> throw new Exception("输入操作符不对:" + item);
                };
                // 再把结果压入栈
                stack.push(String.valueOf(result));
            }
        }
        // 输出最终结果
        System.out.println("计算结果:" + stack.pop());
    }

}
